$\delta$-hyperbolic graphs, originally conceived by Gromov in 1987, occuroften in many network applications; for fixed $\delta$, such graphs are simplycalled hyperbolic graphs and include non-trivial interesting classes of"non-expander" graphs. The main motivation of this paper is to investigate theeffect of the hyperbolicity measure $\delta$ on expansion and cut-size boundson graphs (here $\delta$ need not be a constant), and the asymptotic ranges of$\delta$ for which these results may provide improved approximation algorithmsfor related combinatorial problems. To this effect, we provide constructivebounds on node expansions for $\delta$-hyperbolic graphs as a function of$\delta$, and show that many witnesses (subsets of nodes) for such expansionscan be computed efficiently even if the witnesses are required to be nested orsufficiently distinct from each other. To the best of our knowledge, these arethe first such constructive bounds proven. We also show how to find a largefamily of s-t cuts with relatively small number of cut-edges when s and t aresufficiently far apart. We then provide algorithmic consequences of thesebounds and their related proof techniques for two problems for$\delta$-hyperbolic graphs (where $\delta$ is a function $f$ of the number ofnodes, the exact nature of growth of $f$ being dependent on the particularproblem considered).
展开▼
